package algorithm.dynamic;

public class DynamicProgramming {
    public static void main(String[] args) {
        // 多一个开头(多一行)  方便置0 循环时候好判断
        Goods[] goodsList = {
                new Goods("", 0, 0),
          new Goods("guitar", 1500, 1),
          new Goods("stereo", 3000, 4),
          new Goods("computer", 2000, 3),
          new Goods("iphone", 2500, 1)
        };
        int myWeight = 6;
        // 相当于多一行 多一列 都是0 循环的时候好判断
        int[][] value = new int[goodsList.length][myWeight + 1];

        for (int x = 1; x < goodsList.length; x++) {
            for (int weight = 1; weight < myWeight + 1; weight++) {
                // 商品weight > weight 则直接用上一次的value
                if (goodsList[x].getWeight() > weight) {
                    value[x][weight] = value[x - 1][weight];
                    continue;
                }
                // 商品weight <= weight 比较上一次的value 与 这一次商品的值 + 差出来的weight's 最大 value
                value[x][weight] = Math.max(value[x - 1][weight],
                        goodsList[x].getPrice() + value[x - 1][weight - goodsList[x].getWeight()]);
            }
        }

        for (int[] xData : value) {
            for (int data : xData) {
                System.out.print(data + "\t");
            }
            System.out.println();
        }

    }
}

class Goods {
    private String name;
    private int price;
    private int weight;

    public Goods(String name, int price, int weight) {
        this.name = name;
        this.price = price;
        this.weight = weight;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getPrice() {
        return price;
    }

    public void setPrice(int price) {
        this.price = price;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Goods{" +
                "name='" + name + '\'' +
                ", price=" + price +
                ", weight=" + weight +
                '}';
    }
}
